﻿package list;

import common.Node;

public class 单链表的选择排序 {

	public static Node selectionSort(Node head){
		if(head==null || head.next==null)return head;
		Node tail = null;//排序部分的尾部
		Node cur  = head;//未排序的头部
		Node smallPre = null;//最小节点的前一个节点
		Node small =null;//最小节点
		
		while(cur!=null){
			small = cur;
			smallPre= getSmallestPreNode(cur);
			if(smallPre!=null){
				small = smallPre.next;
				smallPre.next = small.next;
			}
			cur =cur==small?cur.next:cur;
			if(tail==null){
				head = small;
			}else{
				tail.next = small;
			}
			tail = small;
		}
		return head;
	}
	
	/**
	 * 获取当前列表的元素中最小原元素的前一个节点
	 * 
	 * @param head
	 * @return
	 */
	public static Node getSmallestPreNode(Node head) {
		Node small = head;
		Node smallPre = null;
		Node cur = head.next;
		Node pre = head;
		while (cur != null) {
			if (cur.value < small.value) {
				smallPre = pre;
				small = cur;

			}
			pre = cur;
			cur = cur.next;
		}
		return smallPre;
	}
}
